class Solution
{
    int ret = -1000;
public:
    int maxPathSum(TreeNode* root)
    {
        dfs(root);
        return ret;
    }
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int left = max(0, dfs(root->left));
        int right = max(0, dfs(root->right));
        ret = max(ret, root->val + left + right);
        return root->val + max(left, right);
    }
};
class Solution
{
    stack<TreeNode*> pPath;
    stack<TreeNode*> qPath;
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& Path)
    {
        if (root == nullptr) return false;
        Path.push(root);
        if (root == x) return true;
        bool left = GetPath(root->left, x, Path);
        if (left == true) return true;
        bool right = GetPath(root->right, x, Path);
        if (right == true) return true;
        Path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        int psize = pPath.size(), qsize = qPath.size();
        int tmp = psize > qsize ? psize - qsize : qsize - psize;
        while (tmp--)
        {
            if (psize > qsize) pPath.pop();
            else qPath.pop();
        }
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};
class Solution
{
    unordered_map<long long, int> hash;
    long long sum = 0;
    int target;
    int ret;
public:
    int pathSum(TreeNode* root, int targetSum)
    {
        target = targetSum;
        hash[0] = 1;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        sum += root->val;
        if (hash.count(sum - target)) ret += hash[sum - target];
        hash[sum]++;
        dfs(root->left);
        dfs(root->right);
        hash[sum]--;
        sum -= root->val;
    }
};
class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (inorder[rooti] != preorder[previ]) rooti++;
            else break;
        }
        previ++;
        TreeNode* root = new TreeNode(inorder[rooti]);
        root->left = build(preorder, inorder, previ, inbegin, rooti - 1);
        root->right = build(preorder, inorder, previ, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int previ = 0;
        return build(preorder, inorder, previ, 0, preorder.size() - 1);
    }
};
class Solution {
public:
    void flatten(TreeNode* root)
    {
        if (root == nullptr) return;
        _flatten(root);
    }
    TreeNode* _flatten(TreeNode* root)
    {
        if (root == nullptr) return nullptr;
        TreeNode* left = _flatten(root->left);
        TreeNode* right = _flatten(root->right);
        if (left == nullptr)
        {
            root->right = right;
        }
        else
        {
            root->right = left;
            TreeNode* cur = left;
            while (cur->right)
            {
                cur = cur->right;
            }
            cur->right = right;
            root->left = nullptr;
        }
        return root;
    }
};
class Solution {
public:
    vector<int> rightSideView(TreeNode* root)
    {
        vector<int> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                if (sz == 0) ret.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }
        return ret;
    }
};
class Solution
{
    int _k;
    int ret;
public:
    int kthSmallest(TreeNode* root, int k)
    {
        _k = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (root == nullptr || _k == 0) return;
        dfs(root->left);
        _k--;
        if (_k == 0) ret = root->val;
        dfs(root->right);
    }
};